package com.cuijq.datasource;

import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;

public class LinkedList {
    /**
     * 数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，
     * 预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读
     *
     * 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，
     * 导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。
     *
     * 链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。
     *
     *
     * 链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，
     * 所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，
     * 容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）
     */

    /**
    如何基于链表实现 LRU 缓存淘汰算法？我的思路是这样的：我们维护一个有序单链表，
     越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
     1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
     2. 如果此数据没有在缓存链表中，又可以分为两种情况：如果此时缓存未满，则将此结点直接插入到链表的头部；如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
    **/

    public static Map<String,Object> map= new HashMap<String, Object>(4);
    public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
        Node heroNode1 = new Node("宋江");
        Node heroNode2 = new Node("卢俊义");
        Node heroNode3 = new Node("吴用");
        Node heroNode4 = new Node("林冲");
        SingleLikedList singleLikedList = new SingleLikedList();
        singleLikedList.add(heroNode1);
        System.out.println(singleLikedList.listCount());
        singleLikedList.add(heroNode2);
        singleLikedList.add(heroNode3);
        singleLikedList.add(heroNode4);
        singleLikedList.list();

        System.out.println("================初始化之后");

        Node heroNode5 = new Node("宋江");
        if (singleLikedList.find(heroNode5)){
            singleLikedList.findAndDel(heroNode5);

            System.out.println("================删除"+heroNode5.item+"之后");
            singleLikedList.list();
            System.out.println("================将新的"+heroNode5.item+"添加到头接点之后");
            singleLikedList.addHead(heroNode5);
            singleLikedList.list();
            System.out.println(singleLikedList.listCount());
        }else {
            //判断 缓存是否满  不可能出现大于


            if (singleLikedList.listCount()==map.size()){
               Node node=  singleLikedList.findEnd(singleLikedList.listCount());
                singleLikedList.findAndDel(node);
                singleLikedList.addHead(heroNode5);
                singleLikedList.list();
            }else {
                singleLikedList.addHead(heroNode5);
                singleLikedList.list();
            }
        }

    }


    static class SingleLikedList{
        private Node<String> head= new Node(new Node());
        void add(Node node){
           Node temp = head;

           while (true){
               if (temp.next == null){
                   break;
               }
               temp=temp.next;
           }
           temp.next =node;
           map.put((String) node.item,node);
        }

        /**
         * 添加到头
         * @param node
         */
        public void addHead(Node node) {
            Node temp = head;
            node.next=temp.next;
            temp.next=node;

            map.put((String) node.item,node);
        }

        /**
         * 删除尾节点
         */
        public Node findEnd(int countNode){
            if (countNode==0){
                return null;
            }
            int count=0;
            Node temp = head.next;
            while (true){
                count++;
                if (countNode== count){
                    return temp;
                }
                temp=temp.next;
            }
        }

        /**
         * 找到第几个节点
         */

        /**
         * 遍历有多个元素
         */
        public int listCount(){
            int count=0;
            if (head.item==null&&head.next==null){
                return count;
            }
            Node temp = head.next;
            while (true){
                count++;
                if (temp.next==null){
                    return count;
                }
                temp=temp.next;
            }
        }
        /**
         * 遍历元素
         */
        public void list(){
            if (head.next==null){
                System.out.println("链表为空");
                return;
            }
            Node temp = head.next;
            while (true){
                if (temp==null){
                    break;
                }
                System.out.println(temp.item);
                temp=temp.next;
            }
        }

        /**
         * 找到并且删除
         * @param node
         */
        public void findAndDel(Node node){
                Node temp = head.next;
                while (true){
                    if (temp==null){
                        break;
                    }
                    if (temp.item == node.item){
                        head.next= temp.next;
                        map.remove(node.item);
                        break;
                    }
                    if (temp.next!=null && node.item.equals(temp.next.item)){
                        temp.next= temp.next.next;
                        map.remove(node.item);
                        break;
                    }
                    temp=temp.next;
                }

        }

        /**
         * 判断是否有
         * @param node
         */
        public boolean find(Node node){
            if (head.next==null){
                System.out.println("链表为空");
                return false;
            }
            Node temp = head.next;
            while (true){
                if (temp==null){
                    break;
                }
                if (temp.item == node.item){
                    return true;
                }
                if (temp.next!=null && node.item.equals(temp.next.item)){
                    temp.next= temp.next.next;
                    return true;
                }
                temp=temp.next;
            }
            return false;
        }

    }
    private static class Node<E> {
        E item;//节点值
        Node<E> next;//后继节点
        Node(){

        }
        Node(E element){
            this.item = element;
        }
        Node( E element,Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }
}
